public class T {
    public static void main(String[] args) {
        LinkedList l=new LinkedList();
        l.addFirst(1);
        l.addFirst(2);
        l.addFirst(3);
        l.addFirst(4);
        l.addFirst(5);
        l.display();
        System.out.println();
        l.addIndex(2,0);
        l.display();
        l.addLast(9);
        System.out.println();
        l.display();
    }


}


// 2、无头双向链表实现
class LinkedList {
    class ListNode{

        int data;
        ListNode next;
        ListNode prev;

        ListNode(int data){
            this.data=data;
        }




    }

    ListNode head;
    //头插法
    public void addFirst(int data){
        if (head==null){
           head= new ListNode(data);


        }else {

            ListNode node=new ListNode(data);
                head.prev=node;
                node.next=head;
                head=node;

        }
    }
    //尾插法
    public void addLast(int data){
        if (head==null){
            head=new ListNode(data);
        }else {
            ListNode cur=head;

            while (cur.next!=null){
                cur=cur.next;
            }

            ListNode node=new ListNode(data);
            node.prev=cur;
            cur.next=node;

        }
    }
    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data){
        if (index>size()){
            return false;
        }else if(index==size()){
            addLast(data);
            return true;
        }else if(index==0){
            addFirst(data);
            return true;
        }else {
            ListNode node=new ListNode(data);
            ListNode cur=head;

            while (index!=0){

                cur=cur.next;
                index--;
            }
            node.next=cur;
            node.prev=cur.prev;
            cur.prev.next=node;
            cur.prev=node;
            return true;

        }
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        if (head==null){
            return false;
        }else {
            ListNode cur=head;
            while (cur!=null){
                if(cur.data==key){
                    return true;
                }else {
                    cur=cur.next;
                }

            }

            return false;
        }
    }


    //删除第一次出现关键字为key的节点
    public void remove(int key){


        ListNode cur=head;
        while(cur!=null){
            if(cur.data==key){
                break;
            }else {
            cur=cur.next;
        }
        cur.prev.next=cur.next;
        cur.next.prev=cur.prev;
    }
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){


        ListNode cur=head;
        while(cur!=null){
            if(cur.data==key){
                cur.prev.next=cur.next;
                cur.next.prev=cur.prev;
                cur=cur.next;
            }else {
                cur=cur.next;
            }
            cur.prev.next=cur.next;
            cur.next.prev=cur.prev;
        }

    }
    //得到单链表的长度
    public int size(){
        int n=0;
        ListNode cur=head;
        while(cur!=null){
            n++;
            cur=cur.next;
        }
        return n;
    }
    public void display(){
        ListNode cur=head;
        while (cur!=null){
            System.out.print(cur.data+" ");
            cur=cur.next;
        }
    }
    public void clear(){
        head=null;
    }
}
